package com.ifreeee.sort;

import org.junit.Test;
import java.util.Random;

public class ShellSort{

    /**
     * 后移法（最终版）
     * 中间有一段不好理解，代码简单，看不到的细节很多，由shellSort1方法改进
     * @param arr
     */
    public static void shellSort(int[] arr)
    {
        int i, j, k , pre, temp, len;//初始化
        len = arr.length;//数组长度
        for(i = len / 2;i > 0;i /=2){//i代表步长和组数
            for(j = i;j < len;j += 1){//插入排序的步骤
                temp = arr[j];//把要插入的数据先临时存起来
                for(k = j;k >= i;k -= i){//向前寻找合适的位置插入
                    pre = k - i;//得到前一个数的下标
                    if(temp < arr[pre]){//如果要插入的数比前一个数小
                        arr[k] = arr[pre];//把前面一个后移
                    }else{
                        break;
                    }
                }
                arr[k] = temp;//插入
            }
        }
    }

    /**
     * 后移法，这个好理解一点
     * @param arr
     */
    private static void shellSort1(int[] arr)
    {
        int i, j, k , pre, temp, len;//初始化
        boolean isInsert;
        len = arr.length;//数组长度
        for(i = len / 2;i > 0;i /=2){//i代表步长和组数
            for(j = i;j < len;j += 1){//插入排序的步骤
                temp = arr[j];//把要插入的数据先临时存起来
                isInsert = false;
                for(k = j;k >= i;k -= i){//向前寻找合适的位置插入
                    pre = k - i;//得到前一个数的下标
                    if(temp < arr[pre]){//如果要插入的数比前一个数小
                        arr[k] = arr[pre];//把前面一个后移
                    }else{
                        arr[k] = temp;
                        isInsert = true;
                        break;
                    }
                }
                if(!isInsert){
                    arr[k] = temp;
                }
            }
        }
    }

    /**
     * 交换法（效率略低）
     * @param arr
     */
    private static void shellSort2(int[] arr)
    {
        int i, j, k , pre, temp, len;//初始化
        len = arr.length;//数组长度
        for(i = len / 2;i > 0;i /=2){//i代表步长和组数
            for(j = i;j < len;j += 1){//插入排序的步骤
                for(k = j;k >= i;k -= i){
                    pre = k - i;
                    if(arr[k] < arr[pre]){
                        temp = arr[k];
                        arr[k] = arr[pre];
                        arr[pre] = temp;
                    }else{
                        break;
                    }
                }
            }
        }
    }

    @Test
    public void test1(){
        Random r = new Random();//随机数对象
        int num1 = 0;//MutableArray的时间
        int num2 = 0;//ArrayList的时间
        int len = 100000000;//测试的数据量
        int time = 1;
        for(int j = 0;j < time;j += 1){
            //初始化操作
            int[] arr = new int[len];
            int[] arr1 = new int[len];
            for(int i = 0; i < len; i += 1){
                int a =  r.nextInt(len);
                arr[i]  =  a;//
                arr1[i]  =  a;//两个数组数据相同
            }
            //希尔排序无需初始化准备
            long t1 = System.currentTimeMillis();
            //代码一
            ShellSort.shellSort2(arr);
            long t2 = System.currentTimeMillis();
            //代码二
            ShellSort.shellSort(arr1);

            long t3 = System.currentTimeMillis();
            num1 += (t2 - t1);
            num2 += (t3 - t2);
        }

        System.out.println("数据量：" + len + "\n测试次数：" + time);
        System.out.println("希尔排序2 耗时：" + num1 + "\n希尔排序 耗时：" + num2);
        /*
            数据量：10000000
            测试次数：10
            希尔排序2 耗时：23437
            希尔排序 耗时：20846

            数据量：100000000
            测试次数：1
            希尔排序2 耗时：36420
            希尔排序 耗时：31601

            结论：后移法，少两步赋值操作，快那么一些
            改进：无
        */
    }

}
